Target devices such as field programmable gate arrays (FPGAs), application specific integrated circuits (ASICs), and structured ASICs are used to implement large systems that may include million of gates and megabits of embedded memory. The complexity of a large system often requires the use of electronic design automation (EDA) tools to create and optimize a design for the system onto physical target devices. Among the procedures performed by EDA tools in a computer aided design (CAD) compilation flow is hardware description language (HDL) compilation. HDL compilation involves performing synthesis, placement, routing, and timing analysis of the system on the target device.
Cyclic redundancy check (CRC) circuitry, forward error correction (FEC) encoders/decoders, and scramblers/descramblers are circuits implemented frequently in network and data storage and retrieval systems. These circuits utilize large networks of exclusive-OR (XOR) gates with multiple outputs fed by a pool of inputs with an overlapping pattern. For example, a common CRC-32 first step receives 64 data bits and produces 32 outputs, where each output depends on approximately half of the 64 data bits, in a randomized pattern.
In order to implement these types of circuits on a target device such as a field programmable gate array, the circuits need to be decomposed into look-up tables (LUTs) with 6 or fewer inputs. Current compilation procedures have limited time to improve the quality of a design and perform only minimal factoring of large XOR networks for optimization.